/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/best-meeting-point
   @Language: C++
   @Datetime: 19-06-13 11:43
   */

class Solution {
	int minidist(vector<int> &v){
		int dist=0;
		sort(v.begin(),v.end());
		for(int i=0, j=v.size()-1; i<j; dist+=v[j--]-v[i++]);
		return dist;
	}
public:
	/**
	 * @param grid: a 2D grid
	 * @return: the minimize travel distance
	 */
	int minTotalDistance(vector<vector<int> > &grid) {
		// write your code here
		vector<int> rows, cols;
		for(int i=0; i<grid.size(); ++i)
			for(int j=0; j<grid[i].size(); ++j)
				if(grid[i][j]==1){
					rows.push_back(i);
					cols.push_back(j);
				}
		return minidist(rows)+minidist(cols);
	}
};
